from typing import List
"""
    这里展示里回溯算法的层去重，
    使用一个额外变量used，来记录当前层是否已经使用过相同的元素，
"""

class Solution:
    """
    给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
    candidates 中的每个数字在每个组合中只能使用 一次 。
    注意：解集不能包含重复的组合。

    示例 1:
            输入: candidates = [10,1,2,7,6,1,5], target = 8,
            输出:
            [
            [1,1,6],
            [1,2,5],
            [1,7],
            [2,6]
            ]
    """
    def combinationSum2(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans = []
        tem = []
        used = []
        for i in range(len(nums)):
            used.append(0)
        def backTracking(begin,MySum,height):
            if MySum == target:
                ans.append(tem.copy())
                return
            if MySum > target:
                return
            for i in range(begin,len(nums)):
                if i != 0 and nums[i] == nums[i-1] and used[i-1] == 0:continue
                MySum += nums[i]
                tem.append(nums[i])
                used[i] = 1
                backTracking(i+1,MySum,height+1)
                MySum -= tem.pop()
                used[i] = 0
            return
        backTracking(0,0,0)
        return ans